package 图;

import java.util.*;

/**
 * 399. 除法求值
 * 给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。
 * 另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。
 *
 * 返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。
 * 注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。
 * 注意：未在等式列表中出现的变量是未定义的，因此无法确定它们的答案。
 *
 *
 * 思路：
 *  要解决“除法求值”问题，可以使用深度优先搜索（DFS）来遍历变量之间的比值关系。核心思路是将方程式转化为带权有向图，并通过DFS搜索路径计算查询结果：
 *  1、构建图结构：
 *   将每个变量视为图的节点，方程式中的比值作为边的权重（如 a/b=2 对应边 a→b 权重为2，b→a 权重为1/2）。
 *  2、处理查询：
 *   对于每个查询 (x, y)，从 x 出发，通过DFS搜索路径到 y，并将路径上的权重相乘。若存在路径，返回乘积；否则返回 -1.0。
 */
public class L_399 {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        // 构建图的邻接表
        Map<String, Map<String, Double>> graph = buildGraph(equations, values);
        double[] results = new double[queries.size()];

        // 处理每个查询
        for (int i = 0; i < queries.size(); i++) {
            String start = queries.get(i).get(0);
            String end = queries.get(i).get(1);

            // 处理变量不存在的情况
            if (!graph.containsKey(start) || !graph.containsKey(end)) {
                results[i] = -1.0;
                continue;
            }

            // 处理 start 和 end 相同的情况
            if (start.equals(end)) {
                results[i] = 1.0;
                continue;
            }

            // 通过DFS搜索路径
            Set<String> visited = new HashSet<>();
            results[i] = dfs(graph, start, end, visited, 1.0);
        }
        return results;
    }


    // 构建图的邻接表
    private Map<String, Map<String, Double>> buildGraph(List<List<String>> equations, double[] values) {
        Map<String,Map<String, Double>> graph = new HashMap<>();
        for (int i = 0; i < equations.size(); i++) {
            String a = equations.get(i).get(0);
            String b = equations.get(i).get(1);
            double val = values[i];
            // 添加正向边 a → b
            graph.computeIfAbsent(a, k -> new HashMap<>()).put(b, val);
            // 添加反向边 b → a
            graph.computeIfAbsent(b, k -> new HashMap<>()).put(a, 1.0 / val);
        }
        return graph;
    }

    // DFS搜索路径并计算乘积
    private double dfs(Map<String, Map<String, Double>> graph, String current, String target,
                       Set<String> visited, double product) {
        if (current.equals(target)) {
            return product; // 找到目标节点，返回累积乘积
        }
        visited.add(current); // 标记当前节点已访问
        // 遍历所有邻接节点
        for (Map.Entry<String, Double> neighbor : graph.get(current).entrySet()) {
            String next = neighbor.getKey();
            double weight = neighbor.getValue();

            if (!visited.contains(next)) {
                double result = dfs(graph, next, target, visited, product * weight);
                if (result != -1.0) {
                    return result; // 找到有效路径，直接返回
                }
            }
        }

        visited.remove(current); // 回溯，移除当前节点标记
        return -1.0; // 未找到路径
    }
}
